#include <iostream>
using namespace std;

template <typename T>
void qselect_helper(T *arr, int left, int right, int r)
{
    if (left >= right) {
        return;
    }
    T &pivot = arr[left];
    int i = left, j = right;
    while (i < j) {
        while (arr[i] <= pivot && i < right) { i++; }
        while (arr[j] > pivot) { j--; }
        if (i < j) {
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(pivot, arr[j]);
    if (j - left + 1 == r) {
        // XXX: middle case separated, or it is easy to lead to infinite loop with only 2 subarray...
        return;
    }
    if (j - left >= r) {
        qselect_helper(arr, left, j-1, r);
    } else {
        qselect_helper(arr, j+1, right, r-(j+1-left));
    }
}

template <typename T>
void qselect(T *arr, int n, int r)
{
    if (r <= n) {
        qselect_helper(arr, 0, n-1, r);
    }
}

int main()
{
    int a[] = { 8, 11, 3, -1, 22, 5, 42, -12, 32 };
    int n = sizeof(a)/sizeof(a[0]);
    int r = 6;
    qselect(a, n, r);
    for (int i = 0; i < r; i++) {
        cout << a[i] << endl;
    }
    return 0;
}

